This invention relates generally to shared storage hierarchies in multiprocessing systems, and in particular to use of an exclusive dirty status in a coherence protocol to disambiguate ownership and modification status for memory references in a shared multi-level storage hierarchy.
In a multiprocessing system with a shared multi-level storage hierarchy, typically comprising a shared cache storage, one processor may request access from a shared cache storage to data that is in a state of ownership by another processor. The requesting processor does not know if the requested data in the shared cache storage is valid or if it has been modified by another processor in a private storage at another level of the storage hierarchy. Therefore the requested data in the shared cache storage is not useful to the requesting processor until its actual status can be determined. An ambiguous status for data in shared cache storage hierarchies is referred to as a xe2x80x9csharing ambiguity.xe2x80x9d
One method for resolving sharing ambiguities in multiprocessing systems makes use of a common bus to snoop transactions (M. Papamarcos and J. Patel, xe2x80x9cA Low-Overhead Coherence Solution for Multiprocessors with Private Cache Memories,xe2x80x9d Proc. 11th ISCA, 1984 pp. 348-354). Snooping transactions on a common bus to maintain coherence increases traffic to a processor""s private cache storage. This increased traffic is not necessarily related to data that is actually needed by the respective processor. Therefore a disadvantage of snooping is that the average latency of cache accesses is increased since requests for data have to compete with snoops for access to the private caches. Moreover, the competition increases with the number of processors sharing a common bus. As a consequence, overall system performance suffers due to slower average access times. A second disadvantage of snooping can occur because an access to requested data in the shared cache storage must wait until results of snooping are received.
Another method for resolving sharing ambiguities involves broadcasts of inquiries (commonly referred to as disambiguating inquiries or backward inquiries) over an interconnection network shared by the processors with access to the shared cache storage. When requested data is found to be in an ambiguous state, an inquiry is broadcast to the other processors. Again, latency increases since the requesting processor must wait until responses to the broadcast inquiry are received. As the number of processors sharing a cache storage increases, so does the potential number of broadcasts and responsesxe2x80x94contributing to increased network congestion.
In addition to the increases in latency associated with these prior methods, there are also additional costs associated with providing hardware functionality in order to implement a particular chosen method. Hardware functionality requires additional circuitry, and additional circuitry requires increased silicon area. An undesirable secondary effect of additional hardware circuitry and increased silicon area is an increase in the number and severity of critical timing paths, potentially resulting in further performance degradation for the overall system.
Another method used in distributed systems is known as SCI (Scalable Coherent Interface, IEEE Std 1596-1992 Scalable Coherent Interface, Piscataway, N.J.). SCI supports a one-writer-multiple-reader format with a distributed doubly linked list that is maintained through main memory. Addresses of private cache storage are inserted onto the list in a controlled manner and only the address at the head of the list may overwrite the data. The interface maintains a coherent storage hierarchy, by forwarding data requests to the head of the list. One disadvantage of such a system is that before data may be overwritten the list must be sequentially purged. For large distributed systems, delays associated with such a method potentially contribute to performance degradation of the overall system. In addition to the potential for undesirable network congestion inherent in such a distributed system, problematic issues of link maintenance in cases of distributed system failures must also be addressed.